package com.gwcloud.leetcode.tags.greed;

import java.util.Arrays;
import java.util.Comparator;

/** 
* @ClassName   : Leetcode0435 
* @author      : ganwei 
* @date        : 2020年5月17日 
* @Description : 435. 无重叠区间 
*/
public class Leetcode0435 {
    /**
     * -解题思路，贪心算法来一波
     */
	public int eraseOverlapIntervals(int[][] intervals) {
    	int n = intervals.length;
		return n - intervalSchedule(intervals);
    }
	
	/**
	 * -最多有几个区间不重复
	 */
	public int intervalSchedule(int[][] intvs) {
		if( intvs.length == 0) return 0;
	    Arrays.sort(intvs, new Comparator<int[]>() {
	        public int compare(int[] a, int[] b) {
	            return a[1] - b[1];
	        }
	    });
	    
	    int count = 1;
	    int x_end = intvs[0][1];
	    for(int[] intv : intvs) {
	    	int start = intv[0];
	    	if(start >= x_end) {
	    		count ++;
	    		x_end = intv[1];
	    	}
	    }
	    return count;
	}
	
	/**
	 * -主函数
	 */
	public static void main(String[] args) {
		
	}
}
